package com.uow.algdemo.algorithms;

import java.util.ArrayList;
import java.util.List;

import com.uow.algdemo.material.Node;

/**
 * This class will receive a set of numbers and insert into a tree use different
 * algorithms, then generate animation steps.
 */
public class Tree
{
    /**
     * Root node of a tree.
     */
    public Node root;
    /**
     * Array of all data, not in tree.
     */
    private int[] array;
    /**
     * Number of integers.
     */
    private int count;
    /**
     * Return value for creating tree animation.
     */
    private Node btReturn;
    /**
     * List contains steps of tree animation.
     */
    private List<int[][]> steps = new ArrayList<int[][]>();

    public Tree()
    {
    	count = 0;
    }

	/**
	 * @return The steps of solution.
	 */
    public List<int[][]> getSteps()
    {
    	return steps;
    }
    /**
     * This function insert an integer into current binary tree as a complete tree.
     * @param value Value for insert.
     * @return Current binary complete tree.
     */
    public Node insertBinaryTree(int value)
    {
		count++;
		if (count == 1)
		{
		    array = new int[count];
		    array[count - 1] = value;
		}
		else
		{
		    int[] tmparray = new int[array.length];
		    for (int i = 0; i < array.length; i++)
		    {
		    	tmparray[i] = array[i];
		    }
		    array = new int[count];
		    for (int i = 0; i < tmparray.length; i++)
		    {
		    	array[i] = tmparray[i];
		    }
		    array[count - 1] = value;
		}
		root = createCompleteTree(root, array, 1, 0, 0, 0.5);
		return btReturn;
    }
    /**
     * This function insert an integer into a node.
     * @param n Node of parent.
     * @param array Array contains data.
     * @param i Index of data in array.
     * @param level Level of current parent node.
     * @param parent Index of parent in tree.
     * @param position Position of node in animation.
     * @return Current node.
     */
    private Node createCompleteTree(Node n, int[] array, int i, int level, int parent, double position)
    {
		if (i > array.length)
		{
		    return null;
		}
		else
		{
		    int v = array[i - 1];
		    Node tmp = new Node(v, i - 1, level, parent, position);
		    n = tmp;
	
		    n.leftChild = createCompleteTree(n.leftChild, array, 2 * i, level + 1, i - 1, position - Math.pow(0.5, level + 2));
		    n.rightChild = createCompleteTree(n.rightChild, array, 2 * i + 1, level + 1, i - 1, position + Math.pow(0.5, level + 2));
		    if (i == array.length)
		    {
		    	btReturn = n;
		    }
		    return n;
		}
    }
    /**
     * This function insert an integer into current binary search tree.
     * @param value Value for insert.
     * @return Current binary complete tree.
     */
    public Node insertBinarySearchTree(int value)
    {
		if (root == null)
		{
		    Node newNode = new Node(value, count, 0, 0, 0.5);
		    root = newNode;
		    count++;
		    return newNode;
		}
		else
		{
		    Node tmp = root;
		    while (true)
		    {
				if (value < tmp.value)
				{
				    if (tmp.leftChild == null)
				    {
						Node newNode = new Node(value, count, tmp.level + 1, tmp.index, tmp.position - Math.pow(0.5, tmp.level + 2));
						tmp.leftChild = newNode;
						count++;
						return newNode;
				    }
				    else
				    {
				    	tmp = tmp.leftChild;
				    }
				}
				if (value >= tmp.value)
				{
				    if (tmp.rightChild == null)
				    {
						Node newNode = new Node(value, count, tmp.level + 1, tmp.index, tmp.position + Math.pow(0.5, tmp.level + 2));
						tmp.rightChild = newNode;
						count++;
						return newNode;
				    }
				    else
				    {
				    	tmp = tmp.rightChild;
				    }
				}
		    }
		}
    }

    /**
     * This method traverse a tree use in order traverse and records all steps in list of steps.
	 * @param node Node for traverse.
     */
    public void traverseInOrder(Node node)
    {
		if (node == null)
		    return;
	
		traverseInOrder(node.leftChild);
		highlight(node.index);
		traverseInOrder(node.rightChild);
    }

    /**
     * This method traverse a tree use post order traverse and records all steps in list of steps.
	 * @param node Node for traverse.
     */
    public void traversePostOrder(Node node)
    {
		if (node == null)
		    return;
	
		traversePostOrder(node.leftChild);
		traversePostOrder(node.rightChild);
		highlight(node.index);
    }

    /**
     * This method traverse a tree use previous order traverse and records all steps in list of steps.
	 * @param node Node for traverse.
     */
    public void traversePreOrder(Node node)
    {
		if (node == null)
		    return;
	
		highlight(node.index);
		traversePreOrder(node.leftChild);
		traversePreOrder(node.rightChild);
    }
    /**
     * This method records steps for highlight a point.
     * @param index Index of point to highlight in tree.
     */
    private void highlight(int index)
    {
		int[][] tmp = new int[3][1];
		tmp[0][0] = 0;
		tmp[1][0] = index;
		steps.add(tmp);
    }
}
